package clustering.testing;

import java.io.File;
import java.io.FileOutputStream;
import java.util.ArrayList;
import java.util.Hashtable;

import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;

import org.w3c.dom.Document;
import org.w3c.dom.Node;

import clustering.implementations.*;
import clustering.framework.*;

public class BiConstructor {
	 ArrayList alEdges = new ArrayList();
	 public BiConstructor(double [][] dMatrix)throws Exception{
		 UPGMATreeConstructor tc = new UPGMATreeConstructor();
		 //tc.K = 1;
		 qNodes = new QNode[2*dMatrix.length-2];
		 Document xmlTree = getTree(tc,dMatrix);
		 ArrayList alQuartets = Quartet.generateFullQuartetList(dMatrix);
	     QuartetTree qt = constructFromXmlDocument(xmlTree);
	     ArrayList alBestQuartets = Quartet.generateBestQuartetList(dMatrix);
		 TreeEdge te = null;
		 for(int i=0;i<qNodes.length;i++){
			 QNode qn = qNodes[i];
			 boolean br = false;
			 if(qn.label == -1){
				 for(int j=0;j<qn.adj.length;j++){
					 if(qn.adj[j].label == -1){
						 te = new TreeEdge(qn,qn.adj[j]);
						 br = true;
						 break;
					 }
				 }
			 }
			 if(br)break;
		 }
		 partitionTree(qt,te,dMatrix.length);
		 
		 for(int i=0;i<partTable.length;i++){
			 for(int j=0;j<partTable.length;j++){
				 System.out.print(partTable[i][j]+" ");
			 }
			 System.out.println(" ");
		 }
		 
		 int count = 0, mismatch = 0;
		 for(int i=0;i<alQuartets.size();i++){
			 Quartet q = (Quartet)alQuartets.get(i);
			 if(isConsistent(q)==isConsistent(q,qt)){
				 count++;
			 }else{
				 isConsistent(q);
				 mismatch++;
			 }
		 }
		 System.out.print("ok");
	 }

	 int [][] partTable = null;
	 boolean isConsistent(Quartet q){
		 boolean nonDetermination = true;
		 boolean consistent = false;
		 int k = 0;
		 int a = q.nodes[0];
		 int b = q.nodes[1];
		 int c = q.nodes[2];
		 int d = q.nodes[3];
		 int [][] pt = partTable;
		 int [] sum = new int[4];
		 boolean nd1 = false;
		 boolean nd2 = false;
		 while(nonDetermination){
			 sum[0] += pt[a][k];
			 sum[1] += pt[b][k];
			 sum[2] += pt[c][k];
			 sum[3] += pt[d][k];
			 //if(pt[a][k]==pt[b][k] && pt[c][k]==pt[d][k] && pt[a][k]!=pt[c][k]){
			 if(sum[0]==sum[1] && sum[2]==sum[3] && sum[0]!=sum[2]){
				 nonDetermination = false;
				 consistent = true;
			 }else if(pt[a][k]!=pt[b][k] && pt[c][k]!=pt[d][k]){
			 //}else if(sum[0]!=sum[1] && sum[2]!=sum[3]){
				 nonDetermination = false;
				 consistent = false;
			 }else if(sum[2]==sum[3] && sum[2]!=sum[0] && sum[2]!=sum[1]){
				 nonDetermination = false;
				 consistent = true;
			 }else if(pt[c][k]==pt[d][k] && pt[c][k]!=pt[a][k] && pt[c][k]!=pt[b][k]){
				 nonDetermination = false;
				 consistent = true;
			 }else if(sum[0]==sum[1] && sum[0]!=sum[2] && sum[0]!=sum[3]){
				 nonDetermination = false;
				 consistent = true;
			 }else if(pt[a][k]==pt[b][k] && pt[a][k]!=pt[c][k] && pt[a][k]!=pt[d][k]){
				 nonDetermination = false;
				 consistent = true;
			 }else if((pt[a][k]==0 && pt[b][k]==0)||(pt[c][k]==0 && pt[d][k]==0)){
				 nonDetermination = false;
				 consistent = true;
			 }else{
				 if((pt[a][k]!=pt[b][k])){
					 nd1 = true;
					 sum[2] = 0;
					 sum[3] = 0;
					 if(pt[a][k]==pt[c][k]){
						 sum[0]=0;
					 }else{
						 sum[1]=0;
					 }
				 }
				 if((pt[c][k]!=pt[d][k])){
					 nd2 = true;
					 sum[0]=0;
					 sum[1]=0;
					 if(pt[c][k]==pt[a][k]){
						 sum[2]=0;
					 }else{
						 sum[3]=0;
					 }
				 }
				 if(nd1 && nd2){
					 nonDetermination = false;
					 consistent = false;
				 }
			 }
			 k++;
		 }
		 return consistent;
	 }
	 
	 void partitionTree(QuartetTree qt, TreeEdge te, int n){
		 partTable = new int[n][n];
		 int [] partList = new int[n];
		 partList[0]=1;
		 biPart(te.q1,te.q2,partList,0);
		 partList[0]=2;
		 biPart(te.q2,te.q1,partList,0);
	 }
	 void biPart(QNode qn, QNode parent, int [] partList, int depth){
		 if(qn.label != -1){
			 for(int i=0;i<depth;i++){
				 partTable[qn.label][i] = partList[i];
			 }
			 return;
		 }
		 boolean first = true;
		 boolean leaf = false;
		 for(int i=0;i<qn.adj.length;i++){
			 if(qn.adj[i]!=parent){
				 if(first){
					 partList[depth+1]=1;
					 biPart(qn.adj[i],qn,partList,depth+1);
					 first = false;
					 if(qn.adj[i].label != -1)leaf = true;
				 }else{
					 if(leaf){
						 partList[depth+1]=1;
					 }else{
						 partList[depth+1]=2;
					 }
					 biPart(qn.adj[i],qn,partList,depth+1); 
				 }				 
			 }
		 }
	 }
	 	
	 QNode [] qNodes = null;
	 int node_count;
	 QuartetTree constructFromXmlDocument(Document xmlTree){
	      QuartetTree qt = new QuartetTree();
	      QNode qn = new QNode(-1,null,null,null,-1);
	      Node xmlNode = xmlTree.getFirstChild();
	      node_count = 0;
	      for(int i=0;i<xmlNode.getChildNodes().getLength();i++){
		generateTree(xmlNode.getChildNodes().item(i),qn);
	      }
	       if(xmlNode.getChildNodes().getLength()==2){
		    QNode n1 = qn.adj[0];
		    QNode n2 = qn.adj[1];
		    n1.adj[0] = n2;
		    n2.adj[0] = n1;
		    qt.root = n1;
		}else{
		    qNodes[node_count++]=qn;
		    qt.root = qn;
		}        
	       return qt;
	   }
	   void generateTree(Node xmlNode, QNode n0){
	       String sId = xmlNode.getAttributes().getNamedItem("id").getNodeValue();
		int id = Integer.parseInt(sId);
		QNode qn = new QNode(id,n0,null,null,-1);
		if(n0.adj[0]==null)n0.adj[0]=qn;
		else if(n0.adj[1]==null)n0.adj[1]=qn;
		else n0.adj[2]=qn;
		if(xmlNode.hasChildNodes()){
			for(int i=0;i<xmlNode.getChildNodes().getLength();i++){
				generateTree(xmlNode.getChildNodes().item(i),qn);
			}			
		}
		qNodes[node_count++]=qn;
	}
	 
	 Document getTree(IClusterTreeConstructor utc, double [][] dMatrix)throws Exception{
		    String xmlTree = utc.ConstructXMLTree(dMatrix);
			
			FileOutputStream fos = new FileOutputStream("c:\\temp\\test.xml");
			fos.write(xmlTree.getBytes());
			fos.close();
			
			DocumentBuilderFactory docbuilderfact = DocumentBuilderFactory.newInstance();
			DocumentBuilder docbuilder = docbuilderfact.newDocumentBuilder();
			File f = new File("c:\\temp\\test.xml");
			//File f = new File("c:\\temp\\lang\\tree_87.txt");
			return docbuilder.parse(f);
	 }
	 
	 Hashtable htPath = new Hashtable();
	 boolean isConsistent(Quartet q, QuartetTree qt){
	        QNode a = getNodeByLabel(q.nodes[0]);
	        QNode b = getNodeByLabel(q.nodes[1]);
	        QNode c = getNodeByLabel(q.nodes[2]);
	        QNode d = getNodeByLabel(q.nodes[3]);
	        if(htPath.get(a)==null){
	        	htPath.put(a,qt.Dijkstra(a,qNodes));
	        }
	        if(htPath.get(b)==null){
	        	htPath.put(b,qt.Dijkstra(b,qNodes));
	        }
	        if(htPath.get(c)==null){
	        	htPath.put(c,qt.Dijkstra(c,qNodes));
	        }
	        if(htPath.get(d)==null){
	        	htPath.put(d,qt.Dijkstra(d,qNodes));
	        }
	        ArrayList path1 = (ArrayList)((Hashtable)htPath.get(a)).get(b);
	        ArrayList path2 = (ArrayList)((Hashtable)htPath.get(c)).get(d);
	        for(int i=1;i<path1.size()-1;i++){
	            QNode qn1 = (QNode)path1.get(i);
	            for(int j=1;j<path2.size()-1;j++){
	                QNode qn2 = (QNode)path2.get(j);
	                if(qn1 == qn2)return false;
	            }
	        }
	        return true;
	    }
	    QNode getNodeByLabel(int label){
	        for(int i=0;i<qNodes.length;i++){
	            QNode qn = qNodes[i];
	            if(qn.label == label)return qn;
	        }
	        return null;
	    }
}
/*
boolean samePattern(Quartet q, int i, int j){
if(partTable[q.nodes[0]][j]==partTable[q.nodes[1]][j]&&
		 partTable[q.nodes[1]][j]==partTable[q.nodes[2]][j]&&
		 partTable[q.nodes[2]][j]==partTable[q.nodes[3]][j]
		 )return false;
for(int k=0;k<4;k++){
	 if(partTable[q.nodes[k]][i]==0 || partTable[q.nodes[k]][j]==0)return false;
}
if(partTable[q.nodes[0]][i]==partTable[q.nodes[1]][i]){
	if(partTable[q.nodes[0]][i]==partTable[q.nodes[2]][i]){
		if(partTable[q.nodes[0]][j]==partTable[q.nodes[1]][j] && partTable[q.nodes[0]][j]==partTable[q.nodes[2]][j]){
			return true;
		}
	}else if(partTable[q.nodes[0]][i]==partTable[q.nodes[3]][i]){
		if(partTable[q.nodes[0]][j]==partTable[q.nodes[1]][j] && partTable[q.nodes[0]][j]==partTable[q.nodes[3]][j]){
			return true;
		}
	}
}else{
	 	if(partTable[q.nodes[2]][i]==partTable[q.nodes[0]][i]){
			if(partTable[q.nodes[2]][j]==partTable[q.nodes[3]][j] && partTable[q.nodes[2]][j]==partTable[q.nodes[0]][j]){
				return true;
			}
		}else if(partTable[q.nodes[1]][i]==partTable[q.nodes[2]][i]){
			if(partTable[q.nodes[2]][j]==partTable[q.nodes[3]][j] && partTable[q.nodes[2]][j]==partTable[q.nodes[1]][j]){
				return true;
			}
		} 
}
return false;
}
boolean isConsistent(Quartet q){
boolean nonDetermination = true;
boolean nd1 = false, nd2 = false;
boolean consistent = false;
int depth = 0;
if(q.nodes[0]==0 && q.nodes[1]==3 && q.nodes[2]==1 && q.nodes[3]==2){
	 System.out.print("ok");
}
while(nonDetermination){
	 if(nd1 || nd2){
		 if(samePattern(q,depth,depth-1)){
			 nd1 = false;
			 nd2 = false;
		 }else{
			 if(nd1){
				 if(partTable[q.nodes[2]][depth]==0&&partTable[q.nodes[3]][depth]==0){
					 consistent = true;
					 nonDetermination = false;
				 //}else if((partTable[q.nodes[0]][depth]==partTable[q.nodes[2]][depth])||(partTable[q.nodes[0]][depth]==partTable[q.nodes[3]][depth])&&
					//	 (partTable[q.nodes[0]][depth-1]==partTable[q.nodes[2]][depth-1])||(partTable[q.nodes[0]][depth-1]==partTable[q.nodes[3]][depth-1])){
					//nd1 = false;
				 }else if(partTable[q.nodes[0]][depth]==partTable[q.nodes[1]][depth]){
					 if((partTable[q.nodes[2]][depth]==0 || partTable[q.nodes[3]][depth]==0)&&
							 (partTable[q.nodes[2]][depth]==partTable[q.nodes[0]][depth] || partTable[q.nodes[3]][depth]==partTable[q.nodes[0]][depth])){
						 nd1 = false;
					 }else{
						 consistent = true;
						 nonDetermination = false;
					 }
				 }else{
					 consistent = false;
					 nonDetermination = false;
				 }
			 }else if(nd2){
				 if(partTable[q.nodes[0]][depth]==0&&partTable[q.nodes[1]][depth]==0){
					 consistent = true;
					 nonDetermination = false;
				 //}else if((partTable[q.nodes[2]][depth]==partTable[q.nodes[0]][depth])||(partTable[q.nodes[2]][depth]==partTable[q.nodes[1]][depth])&&
				//		 (partTable[q.nodes[2]][depth-1]==partTable[q.nodes[0]][depth-1])||(partTable[q.nodes[2]][depth-1]==partTable[q.nodes[1]][depth-1])){
				//	 nd2 = false;
				 }else if(partTable[q.nodes[2]][depth]==partTable[q.nodes[3]][depth]){
					 if((partTable[q.nodes[0]][depth]==0 || partTable[q.nodes[1]][depth]==0)&&
							 (partTable[q.nodes[0]][depth]==partTable[q.nodes[2]][depth] || partTable[q.nodes[1]][depth]==partTable[q.nodes[2]][depth])){
						 nd2 = false;
					 }else{
						 consistent = true;
						 nonDetermination = false;
					 }
				 }else{
					 consistent = false;
					 nonDetermination = false;
				 }
			 }
		 }
	 }
	 if(nonDetermination){
		 // xx yy
		 if((partTable[q.nodes[0]][depth]==partTable[q.nodes[1]][depth])&&
				 (partTable[q.nodes[2]][depth]==partTable[q.nodes[3]][depth])&&
				 (partTable[q.nodes[1]][depth]!=partTable[q.nodes[2]][depth])
				 //&&
				 //(partTable[q.nodes[0]][depth]!=0)&&
				 //(partTable[q.nodes[2]][depth]!=0)
				 ){
			 consistent = true;
			 nonDetermination = false;
		 }else // xy xy 
			 if((partTable[q.nodes[0]][depth]!=partTable[q.nodes[1]][depth])&&
					 (partTable[q.nodes[2]][depth]!=partTable[q.nodes[3]][depth])
					 //&&
					 //(partTable[q.nodes[0]][depth]!=0)&&
					 //(partTable[q.nodes[2]][depth]!=0)
					 ){
			 consistent = false;
			 nonDetermination = false;
		 }else // xx xy
			 if((partTable[q.nodes[0]][depth]==partTable[q.nodes[1]][depth])&&
					 (partTable[q.nodes[2]][depth]!=partTable[q.nodes[3]][depth])&&
					 ((partTable[q.nodes[1]][depth]==partTable[q.nodes[3]][depth])||
						 (partTable[q.nodes[1]][depth]==partTable[q.nodes[2]][depth]))
				 //&&
				 //(partTable[q.nodes[0]][depth]!=0)
				 ){
			 nd1 = true;
		 }else // xy xx 
			 if((partTable[q.nodes[2]][depth]==partTable[q.nodes[3]][depth])&&
					 (partTable[q.nodes[0]][depth]!=partTable[q.nodes[1]][depth])&&
					 ((partTable[q.nodes[2]][depth]==partTable[q.nodes[1]][depth])||
						 (partTable[q.nodes[2]][depth]==partTable[q.nodes[0]][depth]))
				 //&&
				 //(partTable[q.nodes[2]][depth]!=0)
				 ){
			 nd2 = true;
		 }else if((partTable[q.nodes[0]][depth]==0 || partTable[q.nodes[1]][depth]==0 || partTable[q.nodes[2]][depth]==0 || partTable[q.nodes[3]][depth]==0)){
			 if(partTable[q.nodes[0]][depth]==0 && partTable[q.nodes[1]][depth]==0 && partTable[q.nodes[2]][depth]!=0 && partTable[q.nodes[3]][depth]!=0){
				 consistent = true;
				 nonDetermination = false;
			 }else if(partTable[q.nodes[2]][depth]==0 && partTable[q.nodes[3]][depth]==0 && partTable[q.nodes[0]][depth]!=0 && partTable[q.nodes[1]][depth]!=0){
				 consistent = true;
				 nonDetermination = false;
			 }else if((partTable[q.nodes[0]][depth]==partTable[q.nodes[1]][depth])&&partTable[q.nodes[0]][depth]!=0){
				 consistent = true;
				 nonDetermination = false;
			 }else if((partTable[q.nodes[2]][depth]==partTable[q.nodes[3]][depth])&&partTable[q.nodes[2]][depth]!=0){
				 consistent = true;
				 nonDetermination = false;
			 }else if((partTable[q.nodes[2]][depth]!=partTable[q.nodes[3]][depth])&&partTable[q.nodes[2]][depth]!=0&&partTable[q.nodes[3]][depth]!=0){
				 consistent = false;
				 nonDetermination = false;
			 }else if((partTable[q.nodes[0]][depth]!=partTable[q.nodes[1]][depth])&&partTable[q.nodes[0]][depth]!=0&&partTable[q.nodes[1]][depth]!=0){
				 consistent = false;
				 nonDetermination = false;
			 }
		 }
	 }
	 depth++;
}
return consistent;
}
*/